package com.myc.subjects.stackandqueue;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 *
 * LeetCode题号：225
 *
 * 用队列实现栈
 *
 * 请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
 *
 * 实现 MyStack 类：
 * void push(int x) 将元素 x 压入栈顶。
 * int pop() 移除并返回栈顶元素。
 * int top() 返回栈顶元素。
 * boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
 *
 * 注意：
 * 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
 * 你所使用的语言也许不支持队列。你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列, 只要是标准的队列操作即可。
 *
 * 示例：
 * 输入：
 * ["MyStack", "push", "push", "top", "pop", "empty"]
 * [[], [1], [2], [], [], []]
 * 输出：
 * [null, null, null, 2, 2, false]
 *
 * 解释：
 * MyStack myStack = new MyStack();
 * myStack.push(1);
 * myStack.push(2);
 * myStack.top(); // 返回 2
 * myStack.pop(); // 返回 2
 * myStack.empty(); // 返回 False
 *
 * 提示：
 * 1 <= x <= 9
 * 最多调用100 次 push、pop、top 和 empty
 * 每次调用 pop 和 top 都保证栈不为空
 *
 * 进阶：你能否实现每种操作的均摊时间复杂度为 O(1) 的栈？换句话说，执行 n 个操作的总时间复杂度 O(n) ，尽管其中某个操作可能需要比其他操作更长的时间。你可以使用两个以上的队列。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/implement-stack-using-queues
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

/**
 * 方法一：使用双队列
 * 时间复杂度：push()方法时间复杂度是O(n)，其余都是O(1)
 * 使用两个队列，一个队列模拟栈的使用作为主队列，另一个队列作为辅助队列，用来翻转主队列
 */
public class Yongduilieshixianzhan1 {
    //定一两个双向队列当做队列来使用
    private Deque<Integer> deque1;
    private Deque<Integer> deque2;

    /** Initialize your data structure here. */
    public Yongduilieshixianzhan1() {
        deque1 = new ArrayDeque<>();//初始化双端队列1
        deque2 = new ArrayDeque<>();//初始化双端队列2
    }

    /** Push element x onto stack. */
    public void push(int x) {
        deque2.offer(x);//这里使用offer()方法,在队列2最后追加push的元素

        //将队列1中的元素出队，同时追加到队列2完成翻转
        while(!deque1.isEmpty()){
            deque2.offer(deque1.poll());
        }

        //交换队列1和队列2，保证队列1永远是主队列
        Deque temp = deque1;
        deque1 = deque2;
        deque2 = temp;
    }

    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return deque1.pop();
    }

    /** Get the top element. */
    public int top() {
        return deque1.peek();
    }

    /** Returns whether the stack is empty. */
    public boolean empty() {
        return deque1.isEmpty();
    }

    public static void main(String[] args) {
        Yongduilieshixianzhan1 yongduilieshixianzhan1 = new Yongduilieshixianzhan1();
        yongduilieshixianzhan1.push(1);
        yongduilieshixianzhan1.push(2);
        System.out.println(yongduilieshixianzhan1.top());
        System.out.println(yongduilieshixianzhan1.pop());// 返回 2
        yongduilieshixianzhan1.empty(); // 返回 False
    }
}

//官方题解：
//class MyStack {
//    Queue<Integer> queue1;
//    Queue<Integer> queue2;
//
//    /**
//     * Initialize your data structure here.
//     */
//    public MyStack() {
//        queue1 = new LinkedList<Integer>();
//        queue2 = new LinkedList<Integer>();
//    }
//
//    /**
//     * Push element x onto stack.
//     */
//    public void push(int x) {
//        queue2.offer(x);
//        while (!queue1.isEmpty()) {
//            queue2.offer(queue1.poll());
//        }
//        Queue<Integer> temp = queue1;
//        queue1 = queue2;
//        queue2 = temp;
//    }
//
//    /**
//     * Removes the element on top of the stack and returns that element.
//     */
//    public int pop() {
//        return queue1.poll();
//    }
//
//    /**
//     * Get the top element.
//     */
//    public int top() {
//        return queue1.peek();
//    }
//}

/**
 * 总结：
 * 1.使用两个队列可以实现队列的内容翻转，这样就很容易就能当做栈来使用了
 * 2.注意队列的方法，不要和栈的方法记混了
 */
